package algorithm.leetcode;

import java.util.Arrays;

/**
 * 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
 * <p>
 * 例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
 * <p>
 * 与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
 *
 * @author: zhouj-j
 * @since: 2018/7/6
 */
public class __016_three_sum_closest {
    public int threeSumClosest(int[] nums, int target) {
        if (nums == null || nums.length < 3) {
            return 0;
        }
        Arrays.sort(nums);
        if (nums[0] + nums[1] + nums[2] > target) {
            return nums[0] + nums[1] + nums[2];
        }
        if (nums[nums.length - 1] + nums[nums.length - 2] + nums[nums.length - 3] < target) {
            return nums[nums.length - 1] + nums[nums.length - 2] + nums[nums.length - 3];
        }
        int closet = 0;
        int minDiff = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length - 2; i++) {
            int j = i + 1;
            int k = nums.length - 1;
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                int diff = Math.abs(sum - target);
                if (diff < minDiff) {
                    closet = sum;
                    minDiff = diff;
                }
                if (sum > target) {
                    k--;
                } else if (sum < target) {
                    j++;
                } else {
                    return closet;
                }
            }
        }
        return closet;
    }

    public static void main(String[] args) {
        System.out.println(new __016_three_sum_closest().threeSumClosest(new int[]{-1, 2, 1, -4}, 1));
    }
}
